package com.itcam.countingsort;

import java.util.Arrays;

/**
 * @author : Cammy.Wu
 * Description : 
 */

public class CountingSort {

    public static void main(String[] args) {
        int[] a = {9, 5, 7, 7, 1, 7};
        System.out.println(Arrays.toString(a));
        countingSort(a, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    private static void countingSort(int[] arr, int n) {
        int max = arr[0];
        for (int i = 1; i <= n; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int[] count = new int[max + 1];
        for (int i : arr) { // 这里的i是实际的元素不是索引下标
            count[i]++;
        }
        int j = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[j++] = i;
                count[i]--;
            }
        }
    }


}
